// 07-图4 哈利·波特的考试
#include <stdio.h>
#include <stdlib.h>

/* Array.c =================================*/
int **init2D(int n) {
    int** a = (int**) calloc(sizeof(int*), n);
    for (int i=0; i<n; i++) {
        a[i] = (int*) calloc(sizeof(int), n);
    }
    return a;
}

void free2D(int **a, int n) {
    for (int i=0; i<n; i++) {
        free(a[i]);
    }
    free(a);
}

void print1D(char* name, int array[], int n) {
    printf("%s: ", name);
    for (int i=0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

/* MGraph ====================================*/
// 定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    free2D(g->g, g->vertexNum);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
}

// 从标准输入读取边信息，顶点下标从0开始
void readEdgeV0(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        insertEdge(g, v1, v2, 1);
    }
}

void readEdgeV0WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, v1, v2, dist);
    }
}

// 从标准输入读取边信息，顶点下标从1开始编号
void readEdgeV1(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        insertEdge(g, --v1, --v2, 1);
    }
}

void readEdgeV1WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, --v1, --v2, dist);
    }
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}

/* Floyed =====================================*/
int floyed(MGraph* g, WeightType **d, int **path) {
    // 初始化
    for (int i=0; i<g->vertexNum; i++) {
        for (int j=0; j<g->vertexNum; j++) {
            d[i][j] = g->g[i][j];
            path[i][j] = Connectionless;
        }
    }
    for (int k=0; k<g->vertexNum; k++) {
        for (int i=0; i<g->vertexNum; i++) {
            for (int j=0; j<g->vertexNum; j++) {
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    if (i==j && d[i][j]<0) {
                        // 发现负值圈
                        return 0;
                    }
                    path[i][j] = k;
                }
            }
        }
    }
    return 1;
}

/* current ================================*/

// 找出指定行中的最大值
WeightType findMaxDist(WeightType **d, int i, int vertexNum) {
    WeightType maxDist = 0;
    for (int j=0; j<vertexNum; j++) {
        if (i!=j && d[i][j] > maxDist) {
            maxDist = d[i][j];
        }
    }
    return maxDist;
}

void findAnimal(MGraph *g) {
    // 使用floyed算法，求各点之间的距离
    WeightType **d = init2D(g->vertexNum);
    int **path = init2D(g->vertexNum);
    if (!floyed(g, d, path)) {
        return;
    }
    // printf("d:\n");
    // printD2(d, g->vertexNum);

    int animal;
    WeightType minDist = MaxWeight;
    for (int i=0; i<g->vertexNum; i++) {
        // 找出第i行中的最大值
        WeightType maxDist = findMaxDist(d, i, g->vertexNum);
        if (maxDist == MaxWeight) {
            // 说明有无法连接的节点（有动物无法变）
            printf("0\n");
            return;
        }
        // 再找出各行最大值中的最小值
        if (minDist > maxDist) {
            minDist = maxDist;
            // 最小值所在行即要找到的动物
            animal = i+1;
        }
    }
    printf("%d %d\n", animal, minDist);
    free2D(d, g->vertexNum);
    free2D(path, g->vertexNum);
}

int main() {
    int vertexNum, edgeNum;
    scanf("%d %d", &vertexNum, &edgeNum);
    MGraph* g = createGraph(UndirectedGraph, MaxWeight, vertexNum);
    readEdgeV1WithWeight(g, edgeNum);
    // printGraph(g);
    findAnimal(g);
    freeGraph(g);
    return 0;
}
